package com.ljy.my_study.leetcode.删除链表的倒数第N个结点;

import com.ljy.my_study.util.ListNodeUtil;
import com.ljy.my_study.util.ListNodeUtil.*;

import java.util.Deque;
import java.util.LinkedList;

public class TestMain {

//    给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
//
//    进阶：你能尝试使用一趟扫描实现吗？
//
//             
//
//    示例 1：
//
//
//    输入：head = [1,2,3,4,5], n = 2
//    输出：[1,2,3,5]
//    示例 2：
//
//    输入：head = [1], n = 1
//    输出：[]
//    示例 3：
//
//    输入：head = [1,2], n = 1
//    输出：[1]
//             
//
//    提示：
//
//    链表中结点的数目为 sz
//1 <= sz <= 30
//            0 <= Node.val <= 100
//            1 <= n <= sz
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    public static void main(String[] args) {
    }

    /**
     * 1.栈
     * 2.快慢指针
     * 3.计算链表长度
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode node=head;
        Deque<ListNode> deque=new LinkedList<>();
        while(node!=null){
            deque.addLast(node);
            node=node.next;
        }
        if(deque.size()==n){
            return head.next;
        }
        node=null;
        for(int i=0;i<n;i++){
            node=deque.pollLast();
        }
        ListNode rightNode=node.next;
        ListNode leftNode=deque.pollLast();
        leftNode.next=rightNode;
        return head;
    }
}
